using System;
using System.Collections.Generic;
namespace LeetCode {
    public class LVP {
        public int LongestValidParentheses (string s) {
            if (null == s)
                return 0;
            int len = s.Length;
            int max = 0;
            int[] dp = new int[len];
            for (int idx = len - 2; idx >= 0; idx--) {
                int eidx = idx + 1 + dp[idx + 1];
                if (('(' == s[idx]) && (eidx < len) && (')' == s[eidx])) {
                    dp[idx] = dp[idx + 1] + 2;
                    if (eidx + 1 < len) {
                        dp[idx] += dp[eidx + 1];
                    }
                }
                max = Math.Max (max, dp[idx]);
            }
            return max;
        }
        public int longestValidParentheses (string s) {
            int max = 0, start = 0;
            if (null == s) return 0;

            int len = s.Length;

            Stack<int> stack = new Stack<int> ();
            for (int index = 0; index < len; index++) {
                //遇左括号(，压栈(栈中元素为当前位置所处的下标)
                if ('(' == s[index]) {
                    stack.Push (index);
                    continue;
                } else {
                    if (stack.Count == 0) {
                        start = index + 1;
                        continue;
                    } else {
                        stack.Pop ();
                        if (stack.Count == 0) {
                            max = Math.Max (max, index - start + 1);
                        } else {
                            max = Math.Max (max, index - stack.Peek ());
                        }
                    }
                }
            }
            return max;
        }
    }
}